package com.lsa.helpers.tree.binary;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

import junit.framework.TestCase;

import org.apache.commons.io.IOUtils;
import org.apache.commons.lang.ArrayUtils;

import com.lsa.helpers.Pair;
import com.lsa.helpers.tree.ITreeLabeling;
import com.lsa.helpers.tree.ITreeNode;
import com.lsa.helpers.tree.ITreeVisitor;
import com.lsa.helpers.tree.TgfTreeFactory;

public class TestBinaryTree extends TestCase {
	public void testCreate() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		int[] data = createTestBst(bst);
		for (int i : data) {
			IBinaryTreeNode<Pair<String, Object>> search = bst.search(createTreeValue(i));
			assertNotNull(search);
			assertEquals((Integer)search.getData().getSecond(), Integer.valueOf(i));
		}
		
		int nonExistantValue = Collections.max(Arrays.asList(ArrayUtils.toObject(data))) + 1;
		IBinaryTreeNode<Pair<String, Object>> search = bst.search(createTreeValue(nonExistantValue));
		assertNull(search);
		String path = "data/gen/binaryTree10.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		String expected = IOUtils.toString(new FileInputStream(new File("data/binaryTree10.tgf")));
		assertEquals(expected, actual);
	}
	
	public void testCreateLarge() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		Set<Integer> numbers = new HashSet<Integer>();
		numbers.add(0);
		while(numbers.size() < 50){
			numbers.add((int)(Math.random() * 10000));
		}
		int[] data = ArrayUtils.toPrimitive(numbers.toArray(new Integer[0]));
		for (int i : data) {
			System.out.print(i + " ");
			bst.insert(createTreeValue(i));
		}
		System.out.println();
		Pair<Boolean, IBinaryTreeNode<Pair<String, Object>>> binaryTreeCheckResult = BinaryTreeUtils.isBinaryTree(bst.getRoot(), new INumberConverter<Pair<String, Object>>() {
			@Override
			public Number convert(Pair<String, Object> value) {
				return (Integer)value.getSecond();
			}
		});
		if (!binaryTreeCheckResult.getFirst()){
			String path = "data/gen/binaryTreeCheckFailResult.tgf";
			saveBst(bst, path);
			assertTrue("Not a binary tree", false);
		}
		for (int i : data) {
			IBinaryTreeNode<Pair<String, Object>> search = bst.search(createTreeValue(i));
			assertNotNull(search);
			assertEquals((Integer)search.getData().getSecond(), Integer.valueOf(i));
		}
		
		int nonExistantValue = Collections.max(Arrays.asList(ArrayUtils.toObject(data))) + 1;
		IBinaryTreeNode<Pair<String, Object>> search = bst.search(createTreeValue(nonExistantValue));
		assertNull(search);
		String path = "data/binaryTree50.tgf";
		saveBst(bst, path);
	}

	private Pair<String, Object> createTreeValue(int i) {
		return new Pair<String, Object>(""+i, i);
	}

	private int[] createTestBst(final BinaryTree<Pair<String, Object>> bst) {
		int[] data = new int[]{8,3,10,1,6,14, 4,7,13};
		for(int i : data){
			bst.insert(createTreeValue(i));
		}
		return data;
	}

	public void testRemoveNodesWithInOrderPredecessor4() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(true);
		bst.delete(createTreeValue(4));
		
		String path = "data/binaryTree/gen/binaryTree10_remove4.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove4.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	public void testRemoveNodesWithInOrderPredecessor6() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(true);
		bst.delete(createTreeValue(6));
		
		String path = "data/binaryTree/gen/binaryTree10_remove6_left.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove6_left.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	public void testRemoveNodesWithInOrderPredecessor6Right() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(false);
		bst.delete(createTreeValue(6));
		
		String path = "data/binaryTree/gen/binaryTree10_remove6_right.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove6_right.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	public void testRemoveNodesWithInOrderPredecessor3Left() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(true);
		bst.delete(createTreeValue(3));
		
		String path = "data/binaryTree/gen/binaryTree10_remove3_left.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove3_left.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	public void testRemoveNodesWithInOrderPredecessor3Right() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(false);
		bst.delete(createTreeValue(3));
		
		String path = "data/binaryTree/gen/binaryTree10_remove3_right.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove3_right.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	public void testRemoveNodesWithInOrderPredecessor8Left() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(true);
		bst.delete(createTreeValue(8));
		
		String path = "data/binaryTree/gen/binaryTree10_remove8_left.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove8_left.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	public void testRemoveNodesWithInOrderPredecessor8Right() throws Exception{
		final BinaryTree<Pair<String, Object>> bst = createEmptyBst();
		createTestBst(bst);
		
		bst.setNonDeterministicRemoval(false);
		bst.setDeterministicallyRemoveWithLeft(false);
		bst.delete(createTreeValue(8));
		
		String path = "data/binaryTree/gen/binaryTree10_remove8_right.tgf";
		saveBst(bst, path);
		
		String actual = IOUtils.toString(new FileInputStream(new File(path)));
		path = "data/binaryTree/binaryTree10_remove8_right.tgf";
		String expected = IOUtils.toString(new FileInputStream(new File(path)));
		assertEquals(expected, actual);
	}
	
	private BinaryTree<Pair<String, Object>> createEmptyBst() {
		return new BinaryTree<Pair<String, Object>>(new Comparator<Pair<String, Object>>() {
			@Override
			public int compare(Pair<String, Object> o1,
					Pair<String, Object> o2) {
				return (Integer)o2.getSecond() - (Integer)o1.getSecond();
			}
		});
	}
	private void saveBst(final BinaryTree<Pair<String, Object>> bst,
			String path) throws Exception, IOException {
		saveBst(bst.getRoot(), path);
	}

	private void saveBst(final IBinaryTreeNode<Pair<String, Object>> rootNode,
			String path) throws Exception, IOException {
		class CollectLeftRight implements
				ITreeVisitor<Pair<String, Object>> {
			Set<ITreeNode<Pair<String, Object>>> left = new HashSet<ITreeNode<Pair<String, Object>>>();
			Set<ITreeNode<Pair<String, Object>>> right = new HashSet<ITreeNode<Pair<String, Object>>>();
			@Override
			public void visit(ITreeNode<Pair<String, Object>> n)
					throws Exception {
				IBinaryTreeNode<Pair<String, Object>> node = (IBinaryTreeNode<Pair<String, Object>>)n;
				ITreeNode<Pair<String, Object>> leftSubtree = node.getLeftSubtree();
				if (leftSubtree != null){
					left.add(leftSubtree);
				}
				ITreeNode<Pair<String, Object>> rightSubtree = node.getRightSubtree();
				if (rightSubtree != null){
					right.add(rightSubtree);
				}
			}
		};

		final CollectLeftRight collector = new CollectLeftRight();
		PrefixBinaryTreeWalker<Pair<String, Object>>  walker = new PrefixBinaryTreeWalker<Pair<String, Object>> (collector);
		walker.walk(rootNode);
		TgfTreeFactory.saveStringTreeAsTgf(rootNode, new ITreeLabeling<Pair<String, Object>>(){
			@Override
			public String label(ITreeNode<Pair<String, Object>> node) {
				String label = ""+node.getData().getSecond();
				if (collector.left.contains(node)) label += " L";
				if (collector.right.contains(node)) label += " R";
				return label;
			}}, path);
	}
}
